package 二叉树;

/**
 * 对称二叉树
 * 给定一个二叉树，检查它是否是镜像对称的。
 * User: zhaixiaolong Date:2024/2/23 8:50 ProjectName: algorithm Version:
 */
public class 对称二叉树 {

    static TreeNode initTree() {
        TreeNode root = new TreeNode(1,
                new TreeNode(3, new TreeNode(4), new TreeNode(5)),
                new TreeNode(3, new TreeNode(5), new TreeNode(4)));
        return root;
    }

    public static void main(String[] args) {
        TreeNode root = initTree();
        boolean res = isSymmetric(root);
        System.out.println(res);
    }

    public static boolean isSymmetric(TreeNode treeNode) {
        if (treeNode == null) {
            return false;
        }
        return isSymmetric(treeNode.getLeft(), treeNode.getRight());
    }

    /**
     * 递归算法
     *
     * @param leftNode  左子树
     * @param rightNode 右子树
     * @return 是否对称
     */
    public static boolean isSymmetric(TreeNode leftNode, TreeNode rightNode) {
        // 左右都为空
        if (leftNode == null && rightNode == null) {
            return true;
        }
        // 一个为空一个不为空
        if (leftNode == null || rightNode == null) {
            return false;
        }
        // 左右节点值不一样
        if (leftNode.val != rightNode.val) {
            return false;
        }

        // 递归左右子树
        boolean leftIsSymmetric = isSymmetric(leftNode.getLeft(), rightNode.getRight());
        boolean rightIsSymmetric = isSymmetric(leftNode.getRight(), rightNode.getLeft());

        return leftIsSymmetric && rightIsSymmetric;
    }
}
